package com.ronz.sort;

import java.util.Arrays;

/**
 * @Description 桶排序（基数排序加强版）
 * @Author Ronz
 * @Date 2021/1/12 14:48
 * @Version 1.0
 */
public class No7_RadixSort {

    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};

        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }


    public static void radixSort(int arr[]){
        int[][] bucket = new int[10][arr.length];   // 用一个二维数组来模拟桶，0-9总共十个桶
        int[] bucketCount = new int[10];            // 记录每个桶中的元素数量
        int max = arr[0];
        int arrCount;       // 原数组索引

        /* 获取数组中最大的数 */
        for (int i=1; i<arr.length; i++){
            if (max < arr[i]){
                max = arr[i];
            }
        }
        int length = (max + "").length();   // 获取最大的数的位数

        /* 开始桶排序 */
        for (int k=0, n=1; k<length; k++, n*=10){       // 最大的数位数是多少，就进行多少轮桶排序
            /* 第 k 轮桶排序 */
            for (int i=0; i<arr.length; i++){
                int digit = arr[i]/n%10;    // 获取元素的 个/十/百/...位数
                bucket[digit][bucketCount[digit]] = arr[i];  // 将元素放入桶中，如 4 放入 4号桶
                bucketCount[digit]++;   // 计数器加1，如个位数为4，则4号桶计数器加1
            }

            arrCount = 0;
            /* 将桶中的数据取出来给原数组 */
            for (int i=0; i<10; i++){   // 遍历所有的桶
                if (bucketCount[i] != 0){   // 如果桶不为空，则取数据
                    for (int j=0; j<bucketCount[i]; j++){
                        arr[arrCount++] = bucket[i][j];
                    }
                }
            }
            /* 把桶中的数据清空 */
            bucketCount = new int[10];
        }


//        /* 第一轮桶排序 */
//        for (int i=0; i<arr.length; i++){
//            int digit = arr[i]%10;    // 获取元素的个位数
//            bucket[digit][bucketCount[digit]] = arr[i];  // 将元素放入桶中，如 4 放入 4号桶
//            bucketCount[digit]++;   // 计数器加1，如个位数为4，则4号桶计数器加1
//        }
//
//        arrCount = 0;
//        /* 将桶中的数据取出来给原数组 */
//        for (int i=0; i<10; i++){   // 遍历所有的桶
//            if (bucketCount[i] != 0){   // 如果桶不为空，则取数据
//                for (int j=0; j<bucketCount[i]; j++){
//                    arr[arrCount++] = bucket[i][j];
//                }
//            }
//        }
//        /* 把桶中的数据清空 */
//        bucketCount = new int[10];
//
//        /* 第二轮桶排序 */
//        for (int i=0; i<arr.length; i++){
//            int digit = arr[i]/10%10;       // 获取元素的十位数
//            bucket[digit][bucketCount[digit]] = arr[i];
//            bucketCount[digit]++;
//        }
//        arrCount = 0;
//        /* 将桶中的数据取出来给原数组 */
//        for (int i=0; i<10; i++){   // 遍历所有的桶
//            if (bucketCount[i] != 0){   // 桶不为空时候才取数据
//                for (int j=0; j<bucketCount[i]; j++){ // 遍历当前桶，准备取数据
//                    arr[arrCount++] = bucket[i][j];
//                }
//            }
//        }
//        /* 把桶中的数据清空 */
//        bucketCount = new int[10];
//
//        /* 第三轮桶排序 */
//        for (int i=0; i<arr.length; i++){
//            int digit = arr[i]/10/10%10;       // 获取元素的十位数
//            bucket[digit][bucketCount[digit]] = arr[i];
//            bucketCount[digit]++;
//        }
//        arrCount = 0;
//        /* 将桶中的数据取出来给原数组 */
//        for (int i=0; i<10; i++){   // 遍历所有的桶
//            if (bucketCount[i] != 0){   // 桶不为空时候才取数据
//                for (int j=0; j<bucketCount[i]; j++){ // 遍历当前桶，准备取数据
//                    arr[arrCount++] = bucket[i][j];
//                }
//            }
//        }

    }

}
